<?php
/**
 * @title 44. 通配符匹配 - 优化
 * @author start2004
 */

class Solution {

    /**
     * @param String $s
     * @param String $p
     * @return Boolean
     */
    function isMatch($s, $p) {
        /**
         * @since 2021-08-20 长度
         */
        $lenS = strlen($s);
        $lenP = strlen($p);

        /**
         * @since 2021-08-23 p多个*合并
         */
        $pArray = [];
        $lastChar = "";
        for($i=0; $i<$lenP; $i++){
            if($lastChar == "*" AND $p[$i] == "*"){
            } else {
                $lastChar = $p[$i];
                $pArray[] = $p[$i];
            }
        }
        $p = implode("", $pArray);
        $lenP = count($pArray);

        /**
         * @since 2021-08-23 S为空
         */
        if($lenS == 0){
            if($p == "*" OR $p == ""){
                return true;
            } else {
                return false;
            }
        } else {}

        /**
         * @since 2021-08-23 P为空
         */
        if($lenP == ""){
            return false;
        } else {}

        /**
         * @since 2021-08-20 动态数组
         * @since 2021-08-23 dp[i][j]表示字符串s前i个字符和正则p前j个字符匹配结果
         */
        $dpArray = [];
        $dpArray[0][0] = true;
        if($p[0] == "*"){
            for ($i=0; $i<=$lenS; $i++){
                $dpArray[$i][1] = true;
            }
        } else {}

        /**
         * @since 2021-08-23 迭代
         */
        for($i=1; $i<=$lenS; $i++){
            for($j=1; $j<=$lenP; $j++){
                switch ($p[$j-1]){
                    case "*":
                        if($j == 1){
                            $dpArray[$i][$j] = true;
                        } else {
                            if((isset($dpArray[$i-1][$j]) AND $dpArray[$i-1][$j]) OR (isset($dpArray[$i][$j-1]) AND $dpArray[$i][$j-1])){
                                $dpArray[$i][$j] = true;
                            } else {
                                $dpArray[$i][$j] = false;
                            }
                        }
                        break;
                    case "?":
                        if($j == 1){
                            if($i == 1){
                                $dpArray[$i][$j] = true;
                            } else {
                                $dpArray[$i][$j] = false;
                            }
                        } else {
                            if(isset($dpArray[$i-1][$j-1]) AND $dpArray[$i-1][$j-1] == true){
                                $dpArray[$i][$j] = true;
                            } else {
                                $dpArray[$i][$j] = false;
                            }
                        }
                        break;
                    default:
                        if(($s[$i-1] == $p[$j-1]) AND isset($dpArray[$i-1][$j-1]) AND ($dpArray[$i-1][$j-1] == true)){
                            $dpArray[$i][$j] = true;
                        } else {
                            $dpArray[$i][$j] = false;
                        }
                }
            }
        }
        // var_dump($dpArray);

        /**
         * @return
         */
        return $dpArray[$lenS][$lenP];
    }
}


/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.05_3.php
 */
$datas = [
    ["aa", "a"], // false
    ["aa", "*"], // true
    ["cb", "?a"], // false
    ["adceb", "*a*b"], // true
    ["acdcb", "a*c?b"], // false
    ["", "******"], // true
    ["", ""], // true
    ["a", ""], // false
    ["ho", "**ho"], // true
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->isMatch($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
